package cn.icatw.leetcode.editor.cn;
//你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
//
// 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
//
//
// 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
// 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到
//下一棵树，并继续采摘。
// 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
//
//
// 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
//
//
//
// 示例 1：
//
//
//输入：fruits = [1,2,1]
//输出：3
//解释：可以采摘全部 3 棵树。
//
//
// 示例 2：
//
//
//输入：fruits = [0,1,2,2]
//输出：3
//解释：可以采摘 [1,2,2] 这三棵树。
//如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
//
//
// 示例 3：
//
//
//输入：fruits = [1,2,3,2,2]
//输出：4
//解释：可以采摘 [2,3,2,2] 这四棵树。
//如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
//
//
// 示例 4：
//
//
//输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
//输出：5
//解释：可以采摘 [1,2,1,1,2] 这五棵树。
//
//
//
//
// 提示：
//
//
// 1 <= fruits.length <= 10⁵
// 0 <= fruits[i] < fruits.length
//
//
// Related Topics 数组 哈希表 滑动窗口 👍 629 👎 0


import java.util.HashMap;

//Java：水果成篮
public class T904_FruitIntoBaskets{
    public static void main(String[] args) {
        Solution solution = new T904_FruitIntoBaskets().new Solution();
        int[] fruits1 = {1, 2, 1};
        int[] fruits2 = {0, 1, 2, 2};
        int[] fruits3 = {1, 2, 3, 2, 2};
        int[] fruits4 = {3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4};

        System.out.println(solution.totalFruit(fruits1)); // Output: 3
        System.out.println(solution.totalFruit(fruits2)); // Output: 3
        System.out.println(solution.totalFruit(fruits3)); // Output: 4
        System.out.println(solution.totalFruit(fruits4)); // Output: 5
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int totalFruit(int[] fruits) {
            //初始化变量： 用两个指针 left 和 right 表示滑动窗口的左右边界，用一个哈希表 basket 记录篮子中水果的种类和数量，用一个变量 maxFruits 记录最大水果数目。
            int left = 0, right = 0, n = fruits.length;
            HashMap<Integer, Integer> basket = new HashMap<>();
            int maxFruits = 0;
            /*滑动窗口过程：

            初始化 left 和 right 为 0，表示初始滑动窗口范围为第一个元素。
            遍历数组 fruits，将每个水果加入篮子中，并更新篮子中水果种类的数量。
            如果篮子中水果种类数量超过 2，表示篮子中水果种类不符合要求，需要调整滑动窗口范围：
            将 left 指针右移，直到篮子中水果种类数量恢复到 2 以下。
            在每次调整滑动窗口时，更新 maxFruits 的值，记录最大水果数目。*/
            while (right < n) {
                int fruit = fruits[right];
                basket.put(fruit, basket.getOrDefault(fruit, 0) + 1);
                right++;
                while (basket.size() > 2) {
                    int leftFruit = fruits[left];
                    basket.put(leftFruit, basket.get(leftFruit) - 1);
                    if (basket.get(leftFruit) == 0) {
                        basket.remove(leftFruit);
                    }
                    left++;
                }
                maxFruits = Math.max(maxFruits, right - left);
            }
            //返回结果： 返回 maxFruits 即为收集的最大水果数目。
            return maxFruits;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
